//#define _CRT_SECURE_NO_WARNINGS 1
//
//
//
//
//
//
//
//
//class Solution {
//public:
//    int maxProfit(int k, vector<int>& prices) {
//        int n = prices.size();
//        vector<vector<int>> f(n, vector<int>(k + 1));
//        vector<vector<int>> g(n, vector<int>(k + 1));
//        int ret = 0;
//        f[0][0] = -prices[0];
//        for (int a = 1; a <= k; a++) {
//            f[0][a] = -0x3f3f3f;
//            g[0][a] = -0x3f3f3f;
//        }
//        for (int i = 1; i < n; i++) {
//            for (int j = 0; j <= k; j++) {
//                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
//                g[i][j] = g[i - 1][j];
//                if (j - 1 >= 0) {
//                    g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
//                }
//            }
//        }
//        for (int c = 0; c <= k; c++) {
//            ret = max(ret, g[n - 1][c]);
//        }
//        return ret;
//    }
//};